Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs

Title: Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs
Creator: Mak, Vicky; Boland, Natashia
Relation: International Transactions in Operations Research Vol. 7, Issue 4-5, p. 431-447
Publisher Link: http://dx.doi.org/10.1016/S0969-6016(00)00006-X
Publisher: Wiley-Blackwell
Resource Type: journal article
Date: 2000
Description: The Asymmetric Travelling Salesman Problem with Replenishment Arcs (RATSP) is a new class of problem arising from work related to aircraft routing. This paper describes the problem and presents heuristic approaches for solving the RATSP. We use simulated annealing to obtain feasible solutions, and hence, upper bounds on the optimum value, and solve a Lagrangean dual problem using a subgradient optimization method to obtain lower bounds. While previous methods failed to obtain optimal solutions to some problem classes after 2 h of computation time, with average gaps ranging from 15% to 30%, our heuristic approaches take only 15–20 min to obtain feasible solutions, with gaps of less than 3%. We give computational results comparing these approaches
Subject: combinatorial routing; routing; RATSP; travelling salesman
Identifier: http://hdl.handle.net/1959.13/939480
Identifier: uon:12818
Identifier: ISSN:0969-6016
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format